package _01_动态数组;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/sub-sort-lcci/
 *
 * @Author: haogege
 * @Date: 2021/8/26
 */
public class _面试题_16_16_部分排序 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19};
        _面试题_16_16_部分排序 v = new _面试题_16_16_部分排序();
        int[] ints = v.subSort(nums);
        System.out.println(Arrays.toString(ints));
    }

    // 寻址部分排序，也就是寻址逆序对个数
    public int[] subSort(int[] array) {
        int[] nums = {-1, -1};
        if (array == null || array.length == 0) return nums;
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < max) {
                nums[1] = i;
            } else {
                max = array[i];
            }
        }

        int min = array[array.length - 1];
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] > min) {
                nums[0] = i;
            } else {
                min = array[i];
            }
        }
        return nums;
    }
}
